struct GoldBach {
    last_num: u64,
    double_square: Vec<u64>,
    primes: Vec<u64>,
}

impl GoldBach {
    fn new() -> Self {
        GoldBach {
            last_num: 1,
            double_square: Vec::new(),
            primes: vec![2, 3, 5],
        }
    }

    fn get_double_square(&mut self, n: usize) -> u64 {
        while self.double_square.len() < n {
            let l = self.double_square.len() as u64 + 1;
            self.double_square.push(2 * l * l);
        }
        self.double_square[n - 1]
    }

    fn gen_next_prime(&mut self) {
        for num in self.primes[self.primes.len() - 1] + 1.. {
            let sqrt = (num as f64).sqrt() as u64 + 1;

            for p in &self.primes {
                if *p > sqrt {
                    self.primes.push(num);
                    return;
                }
                if num % p == 0 {
                    break;
                }
            }
        }
    }

    fn get_prime(&mut self, n: usize) -> u64 {
        while self.primes.len() < n {
            self.gen_next_prime();
        }
        self.primes[n - 1]
    }

    fn is_prime(&mut self, num: u64) -> bool {
        let sqrt = (num as f64).sqrt() as u64 + 1;
        for i in 1.. {
            let p = self.get_prime(i);
            if p > sqrt {
                return true;
            }
            if num % p == 0 {
                break;
            }
        }
        false
    }
}

impl Iterator for GoldBach {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            self.last_num += 2;
            if self.is_prime(self.last_num) {
                continue;
            }
            for n in 1.. {
                let ds = self.get_double_square(n);
                if ds > self.last_num {
                    return Some(self.last_num);
                }
                if self.is_prime(self.last_num - ds) {
                    break;
                }
            }
        }
    }
}

pub fn goldbach_conjecture() -> u64 {
    let mut gold_bach = GoldBach::new();
    let n1 = gold_bach.next();
    let n2 = gold_bach.next();
    n1.unwrap() + n2.unwrap()
}
